package or;

import java.util.Arrays;

public class T1397 {

    char[] s1, s2, ev;
    int[][] memo;
    int[] next;
    int MOD = (int) 1e9 + 7;


    public int findGoodStrings(int n, String s1, String s2, String evil) {
        this.s1 = s1.toCharArray();
        this.s2 = s2.toCharArray();
        this.ev = evil.toCharArray();
        memo = new int[s1.length()][evil.length()];
        for (int i = 0; i < s1.length(); i++) {
            Arrays.fill(memo[i], -1);
        }
        next = new int[ev.length];
        for (int i = 1; i < ev.length; i++) {
            int j = next[i - 1];
            while (j > 0 && ev[i] != ev[j]) j = next[j - 1];
            if (ev[i] == ev[j]) j++;
            next[i] = j;
        }
        return dp(0, 0, true, true);
    }

    public int dp(int i, int e, boolean isDownLimit, boolean isUpLimit) {
        if (e == ev.length) {
            return 0;
        }
        if (i == s1.length) {
            return 1;
        }

        if (!isDownLimit && !isUpLimit && memo[i][e] != -1) {
            return memo[i][e];
        }
        long res = 0;
        char down = isDownLimit ? s1[i] : 'a';
        char up = isUpLimit ? s2[i] : 'z';
        for (char j = down; j <= up; j++) {
            int ne = e;
            while (ne > 0 && j != ev[ne]) ne = next[ne - 1];
            if (j == ev[ne]) ne++;
            res = (res + dp(i + 1, ne, isDownLimit && j == s1[i], isUpLimit && j == s2[i])) % MOD;

        }
        if (!isDownLimit && !isUpLimit) {
            memo[i][e] = (int) res;
        }
        return (int) res;
    }
}
